package com.mgq.algorithm.graph;

/**
 * 前缀树 字典树 或者叫trieTree
 */
public class TrieTree {

    private static class TrieNode{
        //表示经过这个node几次
        int pass;
        //该node的结束几次
        int end;
        //当前节点的下级节点
        TrieNode[] nexts;

        public TrieNode() {
            this.pass=0;
            this.end=0;
            //表示26个字符
            this.nexts = new TrieNode[26];
        }
    }

    private static class Trie{
        private TrieNode root;

        public Trie() {
            this.root = new TrieNode();
        }

        /**
         * 加入一个单词
         * 根节点的p表示有多个字符串, 也代表
         *
         * 先将根的node.pass++,表示经过根几次
         * this.nexts= new TrieNode[26], 表示 一开始是26个next.但是这些next都为空
         * 根据加入的字符,来判断对应哪个index,把对应index上的node的pass++(表示经过该node一次)
         * 然后node指向node.next[index].当走完后,把最后一个node.end++表示到这个node结束
         * @param word
         */

        public void insert(String word) {
            if (word == null || "".equals(word)) {
                return;
            }
            TrieNode node = root;
            //先把根pass++
            node.pass++;
            char[] chars = word.toCharArray();
            //char[0]-'a' 就表示某个字母的ASCII码值-'a'的ASCII码, 也就是下标0,表示是a,下标1,表示的是b
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                //表示第一次经过这个node
                if (node.nexts[index] == null) {
                    node.nexts[index] = new TrieNode();
                }
                //node下移
                node = node.nexts[index];
                node.pass++;
            }
            //结束的时候,把node的end++.表示到最后这个字符结束
            node.end++;
        }

        /**
         * 搜索一个单词出现过几次.
         * p值就表示该单词出现过几次
         * @param word
         * @return
         */
        public int search(String word) {
            if (word == null || "".equals(word)) {
                return 0;
            }
            TrieNode node = root;
            char[] chars = word.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                //表示搜索到某个字母时,发现它为空.这时就表示没有这个字符,直接return 0
                if (node.nexts[index]==null) {
                    return 0;
                }
                node=node.nexts[index];
            }
            //表示这个单词出现了几次
            return node.end;
        }

        /**
         * 查询以pre作为前缀的
         * 返回pass即可
         * @param pre
         * @return
         */
        public int prefixNumber(String pre) {
            if (pre == null || "".equals(pre)) {
                return 0;
            }
            TrieNode node = root;
            char[] chars = pre.toCharArray();
            for (int i = 0; i < chars.length; i++) {
                int index = chars[i] - 'a';
                //表示搜索到某个字母时,发现它为空.这时就表示没有这个字符,直接return 0
                if (node.nexts[index]==null) {
                    return 0;
                }
                node=node.nexts[index];
            }
            //表示以pre作为前缀的出现的次数
            return node.pass;
        }

        /**
         * 删除一个单词
         * 将沿途的pass--
         * 将最后节点的end --
         * 有个问题,需要注意删除的单词后面可能有节点,当它的pass变为0时,就没用了,此时就应该把
         * 最后节点的next全部删除
         * 比如 删除abc, 实际有个abcd,如果c的pass为0时,就应该把abdc都删除
         * @param word
         */
        public void delete(String word) {
            //必须先走检查, 比如删除 abcd,但是只加入过abc,如果不搜索,发现删除到一半,结果没这个单词
            if (search(word) != 0) {
                TrieNode node = root;
                char[] chars = word.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    int index = chars[i] - 'a';
                    //先node.nexts[index].pass --
                    //发现等于0了,应该把后续的全部删除
                    if (--node.nexts[index].pass == 0) {
                        //直接把当前头置为null, jvm会回收头为null的node
                        node.nexts[index]=null;
                        return;
                    }
                    node = node.nexts[index];
                }
                node.end--;
            }
        }
    }
}
